package com.tgy.algorithm.base._递归;

public class _01_背包问题01 {


    public static int backpack(int[] weights,int[] values, int index,int restBag) {

        if (index >= weights.length) {
            return 0;
        }

        int value = backpack(weights,values,index+1,restBag);

        int tmpBag = restBag - weights[index];
        int addValue = 0;
        if (tmpBag>= 0) {
            addValue = backpack(weights,values,index + 1,tmpBag)+values[index];
        }

        return Math.max(value,addValue);
    }

    public static int backpack01(int[] weights,int[] values,int index,int restBag) {

        // 创建的默认值为 0
        int[][] cache = new int[weights.length+1][restBag+1];

        for (int i = weights.length-1; i >= 0; i--) {
            for (int j = 0; j <= restBag; j++) {
                int addValue = 0;
                int lastWeight = j - weights[i];
                if (lastWeight >= 0) {
                    addValue = cache[i+1][lastWeight] + values[i];
                }
                cache[i][j] = Math.max(cache[i+1][j],addValue);
            }
        }

        return cache[0][restBag];
    }

    public static void main(String[] args) {

        int[] weights = {2,3,5,7};
        int[] values = {1,5,2,4};
        int backpack01 = backpack01(weights, values, 0, 10);
        System.out.println(backpack01);
    }
}
